---
title: "8、杨辉三角形"
created: 2025-11-28
tags:
  - 算法
---

# 8、杨辉三角形

## 题目 [杨辉三角形](https://www.lanqiao.cn/paper/3829/problem/1457/)

![[image-ff8351c4.png]]

## 思路分析

![[image-188a9243.png]]

以为会是数字三角形模型的线性dp 但看到这个数据范围 n最大1e9 emm dp应该是不可能了

这得线性的算法啊 搞不懂

找一下规律先吧

![[image-62cd3379.png]]

![[image-4e318573.png]]

![[image-5d6fd580.png]]

![[image-188a9243.png]]

要不能构造多少是多少 拿一部分分

![[image-3bb81421.png]]

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1010;

int f[N][N];

int main()

{

	for(int i=1;i<10;i++){

		for(int j=1;j<=i;j++){

			if(i==1)

				f[i][j]=1;

			else if(j==1)

				f[i][j]=1;

			else if(i==j)

				f[i][j]=1;

			else

				f[i][j]=f[i-1][j-1]+f[i-1][j];

			cout<<f[i][j]<<" ";

		}

		cout<<endl;

	}

	return 0;

 }
```

![[image-9d9c01a7.png]]

貌似是没问题的

那然后就是 尽可能枚举多一点 然后枚举到第一个输入的n的时候停止

计算一下它是第几个数

前面分析出来了

(curi,curi)是第 (1+curi)*curi/2个数 (curi,cury)是第 (1+curi)*curi/2 - (curi-curj)个数

所以可以写成

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1010;

int f[N][N];

int main()

{

	int x;cin>>x;

	int curi,curj;

	for(int i=1;i<10;i++){

		bool success=false;

		for(int j=1;j<=i;j++){

			if(i==1)

				f[i][j]=1;

			else if(j==1)

				f[i][j]=1;

			else if(i==j)

				f[i][j]=1;

			else

				f[i][j]=f[i-1][j-1]+f[i-1][j];

//			cout<<f[i][j]<<" ";

			if(f[i][j]==x){

				curi=i,curj=j;

				success=true;

				break;

			}

		}

//		cout<<endl;

		if(success)

			break;

	}

	//(curi,curi)是第 (1+curi)*curi/2个数  (curi,cury)是第 (1+curi)*curi/2 - (curi-curj)个数

	cout<< (1+curi)*curi/2 - (curi-curj);

	return 0;

 }
```

拿6试了一下 对了

![[image-a016d631.png]]

那就这样了 把枚举范围放大一些 但别太贪小心爆空间 一分没有

最后是过了4个 8分 也还行 将近两道填空了呢

![[image-d299db67.png]]

至于正解 大概看了一下 好像是因为有左右对称 然后可以只枚举一半

```cpp
/*   1

   1 2 1

  1 3 3 1

 1 4 6 4 1

1 5 10 10 5 1

可以发现找到第一个出现的一定在左边故右边可以直接删去

           1

         1 2

       1 3

     1 4 6

   1 5 10

 1 6 15 20

/ / / /

从打斜杠的地方可以发现规律为C(2n,n)

故找到最大的斜行

用t来代表斜行数

最大为1e9；

故求有多少个斜行数满足？

int x;//记录第几个斜行满足

for(int t=0;;t++){

  if(1e9<=C(2t,t)){

     x=t;

     break;

  }

}

故解得t=17;

斜线从大到小依次排列第一找到第一个数

再通过二分查找

C(t, k)对应的顺序值为：(t + 1) * t / 2 + k + 1
```

想不到呢 知足了

## 代码实现

```cpp
 #include<bits/stdc++.h>

using namespace std;

const int N=1010;

int f[N][N];

int main()

{

	int x;cin>>x;

	int curi,curj;

	for(int i=1;i<N;i++){

		bool success=false;

		for(int j=1;j<=i;j++){

			if(i==1)

				f[i][j]=1;

			else if(j==1)

				f[i][j]=1;

			else if(i==j)

				f[i][j]=1;

			else

				f[i][j]=f[i-1][j-1]+f[i-1][j];

//			cout<<f[i][j]<<" ";

			if(f[i][j]==x){

				curi=i,curj=j;

				success=true;

				break;

			}

		}

//		cout<<endl;

		if(success)

			break;

	}

	//(curi,curi)是第 (1+curi)*curi/2个数  (curi,cury)是第 (1+curi)*curi/2 - (curi-curj)个数

	cout<< (1+curi)*curi/2 - (curi-curj);

	return 0;

 }
```

```cpp
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

LL n;

LL C(int x,int k){

  LL ans=1;

  for(int i=x,j=1;j<=k;i--,j++){

    ans=ans*i/j;

    if(ans>n)return ans;

  }

  return ans;

}

bool check(int x){

  LL l=2*x,r=max(n,l);

  while(l<r){

    int mid=l+r>>1;

    if(C(mid,x)>=n)r=mid;

    else l=mid+1;

  }

  if(C(r,x)!=n)return false;

  cout<<(LL)(r+1)*r/2+x+1<<endl;

  return true;

}

int main(){

  cin>>n;

  for(int t=17;;t--){

    if(check(t))break;

  }

  return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[7、砝码称重|7、砝码称重]] 🏠 [[00-刷题理模型]] ➡️ [[9、双向排序|9、双向排序]]